package solution;

/**
 * LCR 099. 最小路径和
 * https://leetcode.cn/problems/0i0mDW/description/
 */
class Solution3 {
    public int minPathSum(int[][] grid) {
        //1、创建dp表
        int row = grid.length;//行
        int col = grid[0].length;//列
        if(row == 1 && col == 1) return grid[0][0];//一行一列
        int[][] dp = new int[row + 1][col + 1];
        //2、初始化
        for(int i = 0; i < col + 1; i++) {
            //初始化第一行
            dp[0][i] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < row + 1; i++) {
            //初始化第一列
            dp[i][0] = Integer.MAX_VALUE;
        }
        //dp[0][1],dp[1][0]初始化为0
        dp[0][1] = dp[1][0] = 0;
        //填表
        for(int i = 1; i < row + 1; i++) {
            for(int j = 1; j < col + 1; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][col];
    }
}